Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/cpp_libs/utility.lha/utility/list.C

C/C++ Source or Header | 1993-08-08 | 6KB | 327 lines

/////////////////////////////////////////////////////////////////////
//
// list.C
//
// Package for lists using dynamic arrays.  Allows an element to be
// member of multiple lists simultaneously.
//
// Author:
//
// Dag Bruck, Department of Automatic Control, Lund Institute of Technology,
// Box 118, S-221 00 Lund, Sweden ([e-mail]).
//
// History:
//
// 1987-10-28  DB  First version.
// 1989-07-14  DB  Total reimplementation.
// 1990-02-02  DB  Implemented Remove()!
// 1991-09-06  DB  Changed to pool allocation of small lists.
/////////////////////////////////////////////////////////////////////
//
// $Id: list.C,v 1.4 91/09/06 18:19:05 dag Exp $



#include <list.H>
#include <defs.H>
#include <stdlib.h>
#include <pool.H>
#include <statcount.H>


const int CHUNK_SIZE = 16;


////////////////////////////////////////////////////////////////////
//
// Helper functions for pool management.
//


static Pool* pool;        // zeroed by default in UNIX


inline Pointer* alloc_list(unsigned size)
{
#if 0
  static StatCount cnt("Distribution of list allocation:", 0, 200, 4);
  cnt(size);
#endif

  if (pool == nil) pool = new Pool(CHUNK_SIZE * sizeof(Pointer));

  return size == CHUNK_SIZE ? (Pointer *) pool->alloc() : new Pointer[size];
}


inline void free_list(Pointer* p, unsigned size)
{
  if (size == CHUNK_SIZE)
    pool->free(p);
  else
    delete [] p;
}


////////////////////////////////////////////////////////////////////
//
// Copy pointer array efficiently.
//

inline void copyarray(register Pointer* dst, const register Pointer* src,
              register int n)
{
  while (--n >= 0)
    *(dst++) = *(src++);
}


////////////////////////////////////////////////////////////////////
//
// Constructors and destructors for generic list.
//

GenericList :: GenericList()
    : n(0), size(CHUNK_SIZE)
{
  p = alloc_list(size);
}


GenericList :: GenericList(const GenericList& l)
    : n(l.n), size(l.size)
{
  p = alloc_list(size);
  copyarray(p, l.p, n);
}


GenericList :: ~GenericList()
{
  free_list(p, size);
}


///////////////////////////////////////////////////////////////////
//
// Assignment.
//


void GenericList :: operator = (const GenericList& l)
{
  if (this == &l)        // x = x;
    return;

  n = l.n;
  if (size < n) {
    free_list(p, size);
    size = l.size;
    p = alloc_list(size);
  }
  copyarray(p, l.p, n);
}


///////////////////////////////////////////////////////////////////
//
// Insert element into list (first and last).
//

void GenericList :: Insert(Pointer e)
{
  if (e == nil)            // no-op
    return;

  if (n == size)
    Expand();
  p[n++] = e;
}


void GenericList :: Append(Pointer e)
{
  if (e == nil)            // no-op
    return;

  if (n == size)
    Expand();
  for (register int i = n; i > 0; i--)
    p[i] = p[i-1];
  p[0] = e;
  n++;
}


///////////////////////////////////////////////////////////////////
//
// Append list
//


void GenericList :: Append(const GenericList& l)
{
  if (l.n == 0)            // no-op
    return;

  unsigned new_n = n + l.n;
  if (new_n < size) {        // existing array is big enough
    for (register int i = n-1; i >= 0; i--)
      p[i + l.n] = p[i];
    copyarray(p, l.p, l.n);
    n = new_n;
  }
  else {            // must allocate bigger array
    unsigned new_size = CHUNK_SIZE * ((new_n+CHUNK_SIZE-1) / CHUNK_SIZE);
    // round up to multiple of CHUNK_SIZE
    Pointer* new_p = alloc_list(new_size);

    copyarray(new_p, l.p, l.n);
    copyarray(new_p + l.n, p, n);

    free_list(p, size);
    p = new_p;
    size = new_size;
    n = new_n;
  }
}


///////////////////////////////////////////////////////////////////
//
// Some more operations on lists: Remove, Member, Replace, Reverse.
//


void GenericList :: Remove(Pointer e)
{
  if (n == 0 || e == nil)    // no-op
    return;
  else if (p[n-1] == e)        // simple case
    n--;
  else {
    register int i = 0;
    while (i < n && p[i] != e)
      i++;
    if (i < n) {        // did we find element?
      while (i < n) {
    p[i] = p[i+1];
    i++;
      }
      n--;
    }
  }
}


void GenericList :: RemoveAll()
{
  n = 0;
}


boolean GenericList :: Member(register Pointer e) const
{
  register int i = n;
  register Pointer* q = p;
  while (--i >= 0)
    if (*(q++) == e) return true;

  return false;
}


void GenericList :: Replace(register Pointer old_e, Pointer new_e)
{
  register int i = n;
  register Pointer* q = p;
  while (--i >= 0) {
    if (*q == old_e)
      *q = new_e;
    q++;
  }
}


void GenericList :: Reverse()
{
  register int i = n / 2;
  register Pointer* q1 = p;    // first
  register Pointer* q2 = p+n-1;    // last

  while (--i >= 0) {
    register Pointer t = *q1;
    *(q1++) = *q2;
    *(q2--) = t;
  }
}


///////////////////////////////////////////////////////////////////
//
// Return first, second, third, fourth, fifth, i:th and last elements of list.
//


Pointer GenericList :: First() const
{
  return n < 1 ? nil : p[n-1];
}


Pointer GenericList :: Second() const
{
  return n < 2 ? nil : p[n-2];
}


Pointer GenericList :: Third() const
{
  return n < 3 ? nil : p[n-3];
}


Pointer GenericList :: Fourth() const
{
  return n < 4 ? nil : p[n-4];
}


Pointer GenericList :: Fifth() const
{
  return n < 5 ? nil : p[n-5];
}


Pointer GenericList :: Nth(const int i) const
{
  return i < 1 || n < i ? nil : p[n-i];
}


Pointer GenericList :: Last() const
{
  if (n == 0)
    return nil;
  else
    return p[0];
}


///////////////////////////////////////////////////////////////////
//
// Expand pointer array (copying contents).
//


void GenericList :: Expand()
{
  unsigned new_size = size + CHUNK_SIZE;
  Pointer* new_p = alloc_list(new_size);
  copyarray(new_p, p, n);

  free_list(p, size);
  p = new_p;
  size = new_size;
}